package tree

// https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
// 二叉树的层序遍历
// 时间复杂度: O(n)
// type TreeNode struct {
//     Val int
//     Left *TreeNode
//     Right *TreeNode
// }

func LevelOrder(root *TreeNode) [][]int {
	retArr := make([][]int, 0)
	if nil == root {
		return retArr
	}

	firstLevelNumArr := []int{root.Val}
	lastLevelNodeArr := []*TreeNode{root}
	retArr = append(retArr, firstLevelNumArr)

	for {
		currentLevelNumArr := make([]int, 0)
		currentLevelNodeArr := make([]*TreeNode, 0)
		isAllNull := true

		for _, currentNode := range lastLevelNodeArr {
			if nil != currentNode.Left {
				isAllNull = false
				currentLevelNodeArr = append(currentLevelNodeArr, currentNode.Left)
				currentLevelNumArr = append(currentLevelNumArr, currentNode.Left.Val)
			}
			if nil != currentNode.Right {
				isAllNull = false
				currentLevelNodeArr = append(currentLevelNodeArr, currentNode.Right)
				currentLevelNumArr = append(currentLevelNumArr, currentNode.Right.Val)
			}
		}

		if isAllNull {
			break
		}
		lastLevelNodeArr = currentLevelNodeArr
		retArr = append(retArr, currentLevelNumArr)
	}

	return retArr
}
